import java.util.*;

public class Solution514 {
    public int findRotateSteps(String ring, String key) {
        Map<Character, List<Integer>> map=new HashMap<>();
        for (int i=0;i<ring.length();i++){
            List<Integer> list=map.getOrDefault(ring.charAt(i),new ArrayList<>());
            list.add(i);
            map.put(ring.charAt(i),list);
        }
        int[][] f=new int[key.length()+1][ring.length()];
        for (int[] ints : f) {
            Arrays.fill(ints,Integer.MAX_VALUE);
        }
        f[0][0]=0;
        PriorityQueue<int[]> priorityQueue=new PriorityQueue<>(Comparator.comparingInt(a -> a[2]));
        priorityQueue.offer(new int[]{0,0,0});
        while (!priorityQueue.isEmpty()){
            int[] t=priorityQueue.poll();
            if (t[0]==key.length()){
                return t[2]+key.length();
            }
            List<Integer> list=map.get(key.charAt(t[0]));
            for (Integer integer : list) {
                int move = Math.min(Math.abs(t[1]-integer),ring.length()-Math.abs(t[1]-integer));
                if (f[t[0]+1][integer]>t[2]+move) {
                    priorityQueue.offer(new int[]{t[0]+1,integer,t[2]+move});
                    f[t[0]+1][integer]=t[2]+move;
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution514().findRotateSteps("ababcab","acbaacba"));
    }
}
